#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<unordered_map>

using namespace std;

struct node
{
    int key;
    int value;
    node* prev;
    node* next;
};
class LRUCache {
    unordered_map<int, node*> _table;
    int _capacity;
    node* guard, * tail;
public:
    LRUCache(int capacity)
        :_capacity(capacity)
    {
        guard = new node(-1, -1);
        tail = new node(-1, -1);
        guard->next = tail;
        guard->prev = tail;
        tail->next = guard;
        tail->prev = guard;
    }

    int get(int key) {
        if (_table.count(key))
        {
            auto cur = _table[key];
            cur->prev->next = cur->next;
            cur->next->prev = cur->prev;
            guard->next->prev = cur;
            cur->next = guard->next;
            guard->next = cur;
            cur->prev = guard;
            return cur->value;
        }
        return -1;
    }

    void put(int key, int value) {
        if (_table.count(key))
        {
            auto cur = _table[key];
            _table.erase(key);
            cur->prev->next = cur->next;
            cur->next->prev = cur->prev;
            delete cur;
        }
        if (_table.size() == _capacity)
        {
            auto prev = tail->prev;
            _table.erase(prev->key);
            prev->prev->next = tail;
            tail->prev = prev->prev;
            delete prev;

        }

        auto cur = new node(key, value);
        guard->next->prev = cur;
        cur->next = guard->next;
        cur->prev = guard;
        guard->next = cur;
        _table[key] = cur;
    }
};
